There are very many known techniques of image compression, used to reduce the quantity of data needed to represent an image or a sequence of moving images. Thus, it is sought especially to reduce the bit rates of the digital signals in order to transmit them and/or to store them on a data carrier.
The invention can be applied especially but not exclusively to the transmission of image signals at low bit rate as well as to transmission without bit rate guarantee, as in the case of transmission made according to the IP (“Internet Protocol”).
Among the many known image-encoding methods, it is possible to distinguish especially the ISO-JPEG and ISO-MPEG techniques which have given rise to a standard. These encoding techniques rely especially on the implementation of transforms, enabling the efficient elimination of redundancy in an image.
FIG. 1 illustrates the general principle of a method of encoding by transform.
The image 11 to be encoded is first of all partitioned into a set of non-overlapping rectangular blocks 12 of the same size, to which a invertible transformation 13 is applied. This transformation generates a transformed block 14, formed by a set of transformed coefficients which are less correlated than the coefficients of the original block 12.
These coefficients then undergo a quantification 15 and then an encoding 16 before being transmitted (17) on the channel, or stored.
If the luminance of the pixel having coordinates (x,y) is referenced I(x,y) and if it is assumed that the image to be encoded 11 has been partitioned into M×N sized blocks 12, the application of a block-oriented transformation 13 a(x, y, m, n) will produce an image F with:                               F          ⁡                      (                          m              ,              n                        )                          =                              ∑                          x              =              0                                      M              -              1                                ⁢                                    ∑                              y                =                0                                            N                -                1                                      ⁢                                          I                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                              a                ⁡                                  (                                      x                    ,                    y                    ,                    m                    ,                    n                                    )                                                                                        (        1        )            where m ε [0,M−1] and n ε [0,N−1].
From the transformation a(x, y, m, n), an inverse transformation b(x, y, m, n) can be defined in order to reconstruct the original image I:                               I          ⁡                      (                          x              ,              y                        )                          =                              ∑                          x              =              0                                      M              -              1                                ⁢                                    ∑                              y                =                0                                            N                -                1                                      ⁢                                          F                ⁡                                  (                                      m                    ,                    n                                    )                                            ⁢                              b                ⁡                                  (                                      x                    ,                    y                    ,                    m                    ,                    n                                    )                                                                                        (        2        )            
The main transformations used in image compression are:                the Karhunen Loève transformation (KLT),        the discrete Fourier transformation (DFT),        the discrete cosine transformation (DCT),        and the Walsh-Hadamard transformation (WHT).        
It must be noted that the transformation operation 13, applied by itself, makes no compression of the image since its sole purpose is to decorrelate the original data and concentrate the greatest part of the energy in a small number of transformed coefficients. Since the total energy is preserved, most of the transformed coefficients contain very little energy, and it is therefore the efficient quantification 15 and efficient encoding 16 of these coefficients that will enable the compression.
A high-quality transformation must provide for efficient decorrelation. It must be independent of the processed images and it must possess fast algorithms providing for efficient implementation.
The technique that proves to be most efficient for the decorrelation of a signal is the KLT technique. Unfortunately, it is dependent on the manipulated images (because the statistics of the signal have to be calculated in order to deduce its transform). There are therefore no fast algorithms providing for efficient implementation. This limits its use.
However, for typical images in which there is a strong correlation between the pixels, the performance of the DCT is very close to that of the KLT. Furthermore, the DCT has many fast algorithms providing for efficient implementation. Furthermore, it does not depend on the manipulated images. Finally, it introduces fewer inter-block deformations than the DFT.
If we consider the equation (1), the DCT is obtained by taking:                               a          ⁡                      (                          x              ,              y              ,              m              ,              n                        )                          =                                            2              ⁢                              c                ⁡                                  (                  m                  )                                            ⁢                              c                ⁡                                  (                  n                  )                                                                    MN                                ⁢                      cos            ⁡                          (                                                                    (                                                                  2                        ⁢                        x                                            +                      1                                        )                                    ⁢                  π                  ⁢                                                                          ⁢                  m                                                  2                  ⁢                  M                                            )                                ⁢                      cos            ⁡                          (                                                                    (                                                                  2                        ⁢                        y                                            +                      1                                        )                                    ⁢                  π                  ⁢                                                                          ⁢                  n                                                  2                  ⁢                  N                                            )                                                          (        3        )            With:       c    ⁡          (      w      )        =      {                                        1                          2                                                                          si              ⁢                                                          ⁢              w                        =            0                                                1                          sinon                    
Different compression standards use an approach relying on the DCT, such as JPEG for the fixed images, H261 and H263 for the video sequences with a view to visiophone and visioconference type applications using CIF (Common Intermediate Format) and QCIF (Quarter CIF) format images and finally MPEG (1, 2, and 4) images for video sequences having any contents whatsoever, with a view to digital television type applications.
This standard technique however has several drawbacks due especially to the fact that the processing does not take account of the contents of the original image. Indeed, the partitioning of the image relies on a regular and systematic cutting into squares thus generating the effect of blocks, and does not take the sudden transitions between different zones of the image.
Furthermore, the techniques implementing the transformations lend themselves poorly to geometrical manipulation (zooming-in, rotation or geometrical warping) which are conventionally used to determine the compensation for a motion between two consecutive images in the context of moving images or to obtain the integration of natural images in synthetic scenes.
The invention is designed especially to overcome these drawbacks of the prior art.
More specifically, an object of the invention is to provide a method for the encoding of fixed or moving images based on the implementation of a invertible transformation based on a different partition based on triangles. It must be noted that the simple formulation of this goal amounts to an inventive step. Indeed, at the present time, the main approaches using transforms imply a partitioning into square blocks or a breakdown into regions of any shape but do not provide the flexibility of use of a partition by meshing.
A particular goal of the invention is to provide a method of this kind wherein the triangular partition is adapted to the semantic contents of the image or the sequence of images.
Another goal of the invention naturally is to provide an encoding method of this kind that gives high cost effectiveness of encoding (namely a good ratio between the reconstruction of the image and the quantity of data to be transmitted and stored).
A goal of the invention is also to provide an encoding method of this kind that is relatively easy to implement and especially does not require a large number of additional complex operations as compared with known techniques.
A complementary goal of the invention, in a particular embodiment, is to provide an encoding method of this kind that can be implemented selectively on portions of images as a complement to another approach.
Another goal of the invention is to provide a corresponding decoding method that enables the reconstruction of images simply and at low cost (in terms of processing time, storage capacity, etc.).